\documentclass{beamer}
\usepackage[utf8]{inputenc}
\beamertemplateshadingbackground{red!10}{blue!10}
%\usepackage{fancybox}
\usepackage{epsfig}
\usepackage{verbatim}
\usepackage{url}
%\usepackage{graphics}
%\usepackage{xcolor}
\usepackage{fancybox}
\usepackage{moreverb}
%\usepackage[all]{xy}
\usepackage{listings}
\usepackage{filecontents}
\usepackage{graphicx}

\lstset{
  language=Lisp,
  basicstyle=\scriptsize\ttfamily,
  keywordstyle={},
  commentstyle={},
  stringstyle={}}

\def\inputfig#1{\input #1}
\def\inputeps#1{\includegraphics{#1}}
\def\inputtex#1{\input #1}

\inputtex{logos.tex}

%\definecolor{ORANGE}{named}{Orange}

\definecolor{GREEN}{rgb}{0,0.8,0}
\definecolor{YELLOW}{rgb}{1,1,0}
\definecolor{ORANGE}{rgb}{1,0.647,0}
\definecolor{PURPLE}{rgb}{0.627,0.126,0.941}
\definecolor{PURPLE}{named}{purple}
\definecolor{PINK}{rgb}{1,0.412,0.706}
\definecolor{WHEAT}{rgb}{1,0.8,0.6}
\definecolor{BLUE}{rgb}{0,0,1}
\definecolor{GRAY}{named}{gray}
\definecolor{CYAN}{named}{cyan}

\newcommand{\orchid}[1]{\textcolor{Orchid}{#1}}
\newcommand{\defun}[1]{\orchid{#1}}

\newcommand{\BROWN}[1]{\textcolor{BROWN}{#1}}
\newcommand{\RED}[1]{\textcolor{red}{#1}}
\newcommand{\YELLOW}[1]{\textcolor{YELLOW}{#1}}
\newcommand{\PINK}[1]{\textcolor{PINK}{#1}}
\newcommand{\WHEAT}[1]{\textcolor{wheat}{#1}}
\newcommand{\GREEN}[1]{\textcolor{GREEN}{#1}}
\newcommand{\PURPLE}[1]{\textcolor{PURPLE}{#1}}
\newcommand{\BLACK}[1]{\textcolor{black}{#1}}
\newcommand{\WHITE}[1]{\textcolor{WHITE}{#1}}
\newcommand{\MAGENTA}[1]{\textcolor{MAGENTA}{#1}}
\newcommand{\ORANGE}[1]{\textcolor{ORANGE}{#1}}
\newcommand{\BLUE}[1]{\textcolor{BLUE}{#1}}
\newcommand{\GRAY}[1]{\textcolor{gray}{#1}}
\newcommand{\CYAN}[1]{\textcolor{cyan }{#1}}

\newcommand{\reference}[2]{\textcolor{PINK}{[#1~#2]}}
%\newcommand{\vect}[1]{\stackrel{\rightarrow}{#1}}

% Use some nice templates
\beamertemplatetransparentcovereddynamic

\newcommand{\A}{{\mathbb A}}
\newcommand{\degr}{\mathrm{deg}}

\title{Creating a \commonlisp{} implementation}

\author{Robert Strandh}
\date{March, 2022}

%\inputtex{macros.tex}


\begin{document}
\frame{
\titlepage
\vfill
\small{European Lisp Symposium 2022}
}

\setbeamertemplate{footline}{
\vspace{-1em}
\hspace*{1ex}{~} \GRAY{\insertframenumber/\inserttotalframenumber}
}

\frame{
  \frametitle{The \sicl{} project}
  Thanks to Phoe, \sicl{} stands for:\\ ``\sicl{} Implements \commonlisp{}''.
  \vskip 0.25cm
  A project with the purpose of implementing \commonlisp{} from
  scratch.
}


\frame{
\frametitle{Motivation}
\vskip 0.25cm
\begin{itemize}
\item Dissatisfaction with the way current \commonlisp{}
  implementations are written.
  \begin{itemize}
  \item Insufficient use of CLOS.
  \item Too much implementation-specific code.
  \item Unidiomatic code due to bootstrapping technique.
  \item Deliberately unsafe ``safe code''.
  \end{itemize}
\item Duplication of system code between implementations.
\item Some such instances are justified.  Most are not.
\end{itemize}
}

\frame[containsverbatim]{
\frametitle{Example of existing code}
This is how the slots of the classes \texttt{class} and
\texttt{standard-class} are defined in ECL:
\vskip 0.25cm
\begin{verbatim}
(defparameter +class-slots+
  `(,@+specializer-slots+
    (name :initarg :name :initform nil ...)
    ...
    (direct-subclasses :initform nil ...)
    ...))
\end{verbatim}

\begin{verbatim}
(defparameter +standard-class-slots+
  (append +class-slots+
          '((optimize-slot-access)
            (forward))))
\end{verbatim}
}

\frame[containsverbatim]{
\frametitle{Example of existing code}
These are the equivalent definitions in \sicl{}:
\vskip 0.25cm
\begin{verbatim}
(defclass class (specializer)
  ((%name :initform nil :initarg :name ...)
   ...
   (%direct-subclasses :initform '() ...)))
\end{verbatim}

\begin{verbatim}
(defclass standard-class (class)
  (...))
\end{verbatim}
}

\frame[containsverbatim]{
\frametitle{Example of existing code}
This is how symbols are described in SBCL:
\vskip 0.25cm
\begin{verbatim}
(define-primitive-object
    (symbol :lowtag other-pointer-lowtag
            :widetag symbol-header-widetag
            :alloc-trans %make-symbol
            :type symbol)
  ...
  (name :ref-trans symbol-name :init :arg)
  (package :ref-trans symbol-package
           :set-trans %set-symbol-package
           :init :null)
  ...)
\end{verbatim}
}

\frame[containsverbatim]{
\frametitle{Example of existing code}
This is how symbols are described in \sicl{}:
\vskip 0.25cm

\begin{verbatim}
(defclass symbol (t)
  ((%name :reader symbol-name)
   (%package :reader symbol-package :writer ...))
  (:metaclass built-in-class))
\end{verbatim}
}

\frame{
\frametitle{Why not improve an existing implementation?}
\vskip 0.25cm
Instead of starting from scratch, why not improve an existing
\commonlisp{} implementation?
\vskip 0.25cm
\begin{itemize}
\item The effort would be comparable or perhaps even greater.
\item Maintainers of existing implementations would not accept
  suggestions, so existing code would have to be forked.
\item Some required changes influence large amounts of code.
\end{itemize}
}

\frame{
\frametitle{Initial idea}
\vskip 0.25cm
Create a set of \emph{modules} that can be used to create a complete
\commonlisp{} implementation from a minimal \emph{core}.
\vskip 0.25cm
Problem:
\begin{itemize}
\item Modules must be ordered by dependency.
\item Each module can use only a subset of the language, determined by
  the modules it depends on.
\item Using a subset makes the code unidiomatic.
\item Using a subset also makes modules hard to maintain.
\end{itemize}

}

\frame{
\frametitle{New idea}
Use the full \commonlisp{} language to implement each module.
\vskip 0.25cm
Including:
\vskip 0.25cm
\begin{itemize}
\item Generic functions defined with \texttt{defgeneric} and \texttt{defmethod}.
\item Standard classes defined with \texttt{defclass}.
\item The \texttt{loop} macro.
\end{itemize}
\vskip 0.25cm
And one such module is \clos{}.  More about \clos{} later.
}

\frame{
\frametitle{Consequences of new idea}
Some code must be executed in a \emph{host} during
bootstrapping.
\vskip 0.25cm
In particular, macro expanders of basic target macros.
\vskip 0.25cm
Fortunately, most macro expanders can be written as portable
\commonlisp{} code.
}

\frame{
\frametitle{Consequences of new idea}
Worse: some \emph{target-specific} code must be executed in the host
during bootstrapping.
}

\frame{
  \frametitle{New techniques}
\vskip 0.25cm
\begin{itemize}
\item First-class global environments.
\item Fast generic dispatch.
\item Handling \texttt{:from-end} better.
\item Macros for simplifying sequence functions.
\item Satiation (computing complete discriminating functions).
\item Path replication.
\item Partial inlining.
\item Call-site optimization.
\item Garbage collector.
\item Debugging support.
\end{itemize}
}

\frame[containsverbatim]{
\frametitle{Example of sequence function}
\vskip 0.25cm
\begin{verbatim}
(defmethod position (item (list list) &key ...)
  (with-test-function (test test test-not)
    (with-key-function (key key)
      (for-each-relevant-cons 
          (cons index list start end from-end)
        (let ((element (car cons)))
          (when (test item (key element))
            (return-from position index)))))))
\end{verbatim}
}

\frame{
\frametitle{Implementing CLOS}
\vskip 0.25cm
Most \commonlisp{} implementations probably use a derivative of PCL.
\vskip 0.25cm
But PCL was explicitly written to be bolted onto a pre-ANSI
\commonlisp{} system.
\vskip 0.25cm
As it turns out, CLOS is best described as the result of executing
CLOS code.
\vskip 0.25cm
So we need a way to execute \sicl{}-specific code in the host during
bootstrapping.
\vskip 0.25cm
Our solution is described in our 2019 ELS paper.
}

\frame{
\frametitle{Implementing CLOS}
\vskip 0.25cm
The AMOP book has a chapter ``Living with Circularity''.
\vskip 0.25cm
Two problems: ``bootstrapping'' and ``metastability''.
\vskip 0.25cm
They solve the problem with special-purpose code.
\vskip 0.25cm
We use our technique called ``satiation'' from our paper at ILC 2014.
\vskip 0.25cm
We pre-load the call history with all combinations that have a
resulting effective method.
}

\frame{
\frametitle{Initial modules}
\vskip 0.25cm
\begin{itemize}
\item \texttt{format}
\item \texttt{loop}
\end{itemize}
\vskip 0.25cm
Both use generic functions and standard classes.
}

\frame{
\frametitle{Extracted modules}
\vskip 0.25cm
\begin{itemize}
\item Concrete Syntax Tree
\item Eclector (\texttt{read} and more)
\item Cleavir version 2
\item Clostrum (first-class global environments)
\item Trucler (lexical environments)
\item Incless (printer)
\item Inravina (pretty printer)
\item Cyclosis (streams)
\item Cluster (assembler)
\end{itemize}
}

\frame{
  \frametitle{Concrete syntax tree}
\vskip 0.25cm
\begin{itemize}
\item Started life as a \sicl{} module.
\item Defines standard classes for wrapping S-expressions so that
  additional information can be included.
\item In particular, information about source location can be added.
\item Now, a separate repository.
\end{itemize}
}

\frame{
  \frametitle{Eclector}
\vskip 0.25cm
\begin{itemize}
\item Started life as the \sicl{} reader.
\item Need to read source into Concrete Syntax Trees.
\item For second Climacs, we also wanted to read skipped material such
  as comments and material omitted by reader macros.
\item Now, Eclector is a stable, configurable reader that is
  independent of any implementation.
\end{itemize}
}

\frame{
  \frametitle{Compiler framework (Cleavir)}
\vskip 0.25cm
\begin{itemize}
\item Creation of an Abstract Syntax Tree (AST) from a Concrete Syntax
  Tree (CST).
\item Creation of High-level Intermediate Representation (HIR) from an
  AST.  HIR is a traditional flow graph, with the restriction that every
  variable contains a \commonlisp{} object.
\item Creation of Medium-level Intermediate Representation (MIR) from
  HIR.  MIR introduces explicit memory operations, so some objects are
  raw addresses and raw integers.
\item Creation of Low-level Intermediate Representation (LIR) from
  MIR.  LIR introduces registers, so it is backend specific.
\item Register allocation.
\item Code generation.
\end{itemize}
}

\frame{
  \frametitle{Compiler framework (Cleavir)}
Cleavir currently exists in two versions:
\vskip 0.25cm
\begin{itemize}
\item One version is in the SICL repository.
\item A newer version has been extracted and lots of work has been
  done to it: https://github.com/s-expressionists/Cleavir
\end{itemize}
\vskip 0.25cm
Why?
\begin{itemize}
\item Clasp needed improvements, whereas \sicl{} needed stability.
\item The IR of the newer version maintains basic blocks.
\item \sicl{} may use the newer version, but not right away.\\
  (more details later).
\end{itemize}
}

\frame{
  \frametitle{Clostrum}
\vskip 0.25cm
Alternative spelling for ``claustrum'' which means ``room''.
\vskip 0.25cm
\begin{itemize}
\item First-class global environments.
\item Initial protocol in our 2015 ELS paper.
\item Created for the purpose of \sicl{} bootstrapping, so as to avoid
  package renaming (used by SBCL for instance).
\item Also meant to be an explicit feature of \sicl{}.
\end{itemize}
}

\frame{
  \frametitle{Trucler}
\vskip 0.25cm
\begin{itemize}
\item Lexical environments.
\item CLOS version of the CLtL2 environment protocol.
\end{itemize}
\vskip 0.25cm
Paper presented yesterday.
}

\frame{
  \frametitle{Incless}
\vskip 0.25cm
\begin{itemize}
\item Methods on \texttt{print-object}
\item Currently trampolines to \texttt{print-object-with-client}, but
  we may need to rethink this design.
\end{itemize}
}

\frame{
  \frametitle{Inravina}
\vskip 0.25cm
\begin{itemize}
\item Pretty printer
\item Much better written and with more features that the typical
  pretty printer.
\end{itemize}
}

\frame{
  \frametitle{Cyclosis}
\vskip 0.25cm
\begin{itemize}
\item Classes and methods for streams.
\item Extracted from Mezzano.
\end{itemize}
}

\frame{
  \frametitle{Cluster, the assembler with a difference}
\vskip 0.25cm

Observation: The main task of an assembler (at least for a CISC) is to
turn abstract instructions such as ADD into machine code, depending on
the arguments.  Parsing text and producing object code in a file are
secondary tasks.
\vskip 0.25cm
What Cluster does:
\begin{itemize}
\item It takes a list of standard objects, each representing an
  instruction or a label.
\item It returns a vector of bytes that represents the machine code.
\end{itemize}
\vskip 0.25cm
This way, the compiler does not have to generate text that then has to
be parsed.
}

\frame{
\frametitle{Current state}
\begin{itemize}
\item Bootstrapping mostly working.
\item \texttt{eval} semantics is used during bootstrapping.  Change to
  file-compilation semantics.
\item Different external modules have different conflicting
  requirements.  Fix by using one first-class global environment per
  external module during bootstrapping.
\item Simple call-site manager still not written.
\end{itemize}

}

\frame{
\frametitle{Future work}
\vskip 0.25cm
Extract more modules into separate repositories:
\vskip 0.25cm
\begin{itemize}
\item \texttt{format}
\item \texttt{loop}
\item \texttt{sequence functions}
\item \texttt{high-level list functions}
\item \texttt{hash tables?}
\end{itemize}
}

\frame{
\frametitle{Future work}
\vskip 0.25cm
Use the library ``s-expression-syntax'' by Jan Moringen.  It provides
parsers for:
\vskip 0.25cm
\begin{itemize}
\item Special forms.
\item Lambda lists.
\item Declarations.
\item Type specifiers
\item Standard macros, including \texttt{loop}.
\end{itemize}
\vskip 0.25cm
It would eliminate lots of \sicl{}-specific code.  However:
\vskip 0.25cm
\begin{itemize}
\item Jan Moringen does not consider it quite finished.
\item It depends on two more non-trivial external libraries:
  \begin{itemize}
  \item parser.packrat (which depends on yet others)
  \item architecture.builder-protocol
  \end{itemize}
  which complicates bootstrapping.
\end{itemize}
}

\frame{
\frametitle{Future work}
\vskip 0.25cm
(Research) Investigate the relationship between
static-single-assignment form (SSA) and global value numbering (GVN).
We think the latter might be strictly more general than the former.
\vskip 0.25cm
\begin{itemize}
\item Have the register allocator work on the result of global value
  numbering rather than on lexical locations.
\item Allow the register allocator to do rematerialization.
\item Compare with Cliff Click's ``sea of nodes'' representation.
\item This is the reason \sicl{} might not use the new version of Cleavir.
\end{itemize}
}

\frame{
\frametitle{Projects based on \sicl{}}
\begin{itemize}
\item CLOSOS.  A multi-user operating system with first-class global
  environments for isolation between users or different roles of the
  same user.
\item Second Climacs.  Eclector is already used to parse the buffer
  contents.  We think Cleavir could be used for further analyses at
  typing speed.
\end{itemize}
}

\frame{
  \frametitle{Looking for maintainers}

  We are looking for maintainers for the following modules, which
  either already exist as separate repositories, or that should be
  extracted to separate repositories.

  \begin{itemize}
  \item Clostrum (extracted)
  \item Trucler (extracted)
  \item \texttt{loop} (not yet extracted)
  \item \texttt{format} (not yet extracted)
  \end{itemize}
}

\frame{
\frametitle{Collaborators}
\begin{itemize}
\item Alex Wood (Cleavir, CST, ctype)
\item Charles Zhang (Cleavir, CST)
\item Jan Moringen (Eclector, CST)
\item Marco Heisig (HIR evaluator, sequence functions, Trucler, CST)
\item Hayley Patton (hash tables)
\item Daniel Kochma\'nski (Clostrum)
\item lonjil (Incless)
\item Sylvia Harrington (Cyclosis)
\item Tarn Burton (Inravina)
\item Gnuxie (Cluster, in particular the disassembler)
\end{itemize}
}

\frame{
  \frametitle{Looking for collaborators}

  I would like for at least one other person to understand
  the bootstrapping technique.
}

\frame{
\frametitle{Thank you}
}

%% \frame{\tableofcontents}
%% \bibliography{references}
%% \bibliographystyle{alpha}

\end{document}
